home *** CD-ROM | disk | FTP | other *** search
/ Personal Computer World 2009 February / PCWFEB09.iso / Software / Linux / Kubuntu 8.10 / kubuntu-8.10-desktop-i386.iso / casper / filesystem.squashfs / usr / lib / python2.5 / bisect.py < prev    next >
Text File  |  2008-10-05  |  2KB  |  85 lines
  1. """Bisection algorithms."""
  2.  
  3. def insort_right(a, x, lo=0, hi=None):
  4.     """Insert item x in list a, and keep it sorted assuming a is sorted.
  5.  
  6.     If x is already in a, insert it to the right of the rightmost x.
  7.  
  8.     Optional args lo (default 0) and hi (default len(a)) bound the
  9.     slice of a to be searched.
  10.     """
  11.  
  12.     if hi is None:
  13.         hi = len(a)
  14.     while lo < hi:
  15.         mid = (lo+hi)//2
  16.         if x < a[mid]: hi = mid
  17.         else: lo = mid+1
  18.     a.insert(lo, x)
  19.  
  20. insort = insort_right   # backward compatibility
  21.  
  22. def bisect_right(a, x, lo=0, hi=None):
  23.     """Return the index where to insert item x in list a, assuming a is sorted.
  24.  
  25.     The return value i is such that all e in a[:i] have e <= x, and all e in
  26.     a[i:] have e > x.  So if x already appears in the list, a.insert(x) will
  27.     insert just after the rightmost x already there.
  28.  
  29.     Optional args lo (default 0) and hi (default len(a)) bound the
  30.     slice of a to be searched.
  31.     """
  32.  
  33.     if hi is None:
  34.         hi = len(a)
  35.     while lo < hi:
  36.         mid = (lo+hi)//2
  37.         if x < a[mid]: hi = mid
  38.         else: lo = mid+1
  39.     return lo
  40.  
  41. bisect = bisect_right   # backward compatibility
  42.  
  43. def insort_left(a, x, lo=0, hi=None):
  44.     """Insert item x in list a, and keep it sorted assuming a is sorted.
  45.  
  46.     If x is already in a, insert it to the left of the leftmost x.
  47.  
  48.     Optional args lo (default 0) and hi (default len(a)) bound the
  49.     slice of a to be searched.
  50.     """
  51.  
  52.     if hi is None:
  53.         hi = len(a)
  54.     while lo < hi:
  55.         mid = (lo+hi)//2
  56.         if a[mid] < x: lo = mid+1
  57.         else: hi = mid
  58.     a.insert(lo, x)
  59.  
  60.  
  61. def bisect_left(a, x, lo=0, hi=None):
  62.     """Return the index where to insert item x in list a, assuming a is sorted.
  63.  
  64.     The return value i is such that all e in a[:i] have e < x, and all e in
  65.     a[i:] have e >= x.  So if x already appears in the list, a.insert(x) will
  66.     insert just before the leftmost x already there.
  67.  
  68.     Optional args lo (default 0) and hi (default len(a)) bound the
  69.     slice of a to be searched.
  70.     """
  71.  
  72.     if hi is None:
  73.         hi = len(a)
  74.     while lo < hi:
  75.         mid = (lo+hi)//2
  76.         if a[mid] < x: lo = mid+1
  77.         else: hi = mid
  78.     return lo
  79.  
  80. # Overwrite above definitions with a fast C implementation
  81. try:
  82.     from _bisect import bisect_right, bisect_left, insort_left, insort_right, insort, bisect
  83. except ImportError:
  84.     pass
  85.